package com.acwing.partition2;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/1/2 9:18
 */
public class AC166数独 {

    private static final int N = 9;
    private static int[][] board = new int[N][N];
    private static int[] row = new int[N], col = new int[N], cell = new int[N];
    private static int[] lowbitNum = new int[1 << N], oneCount = new int[1 << N];

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        init();
        while (true) {
            String s = reader.readLine();
            if ("end".equals(s)) break;
            int n = 0;
            //初始化row、col、cell为 1111 1111  表示数字0~8均可用
            for (int i = 0; i < N; i++) row[i] = col[i] = cell[i] = (1 << N) - 1;
            //转输出字符为数字 1~9偏移一位到0~8 待填位置赋值-2以作区分
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (s.charAt(i * N + j) == '.') {
                        board[i][j] = -2;
                        n++;
                    } else {
                        board[i][j] = s.charAt(i * N + j) - '1';
                        //标记对应的行、列、3×3格子对应的数已经使用过，使用过的用0表示
                        setOrRecoverBoard(i, j, board[i][j]);
                    }
                }
            }
            if (dfs(n)) {
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        writer.write((board[i][j] + 1) + "");
                    }
//                    writer.write("\n");
                }
                writer.write("\n");
            }
        }
        writer.flush();
    }

    private static boolean dfs(int surplus) {
        //全部都已经填完
        if (surplus == 0) return true;
        //找到棋盘上分支数最小的一个空格，也就是可选值最少的格子
        int x = -1, y = -1, minOne = 0x3f3f3f3f;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] < 0) {
                    //这个位置是空，得到这个位置可以填的数的状态
                    int status = getStatus(i, j);
                    //如本格可选方案为0 证明无可填数字 本方案无解
                    if (oneCount[status] == 0) return false;
                    if (oneCount[status] < minOne) {
                        minOne = oneCount[status];
                        x = i;
                        y = j;
                    }
                }
            }
        }
        //现在(x,y)就是分支最少，要先搜索的空格子，遍历每个1的位置，相当于遍历这个格子可以填的所有数字
        for (int i = getStatus(x, y); i > 0; i -= lowbit(i)) {
            //得到这个位置上合法的数字
            int num = lowbitNum[lowbit(i)], temp = board[x][y];
            board[x][y] = num;
            setOrRecoverBoard(x, y, num);
            if (dfs(surplus - 1)) return true;
            //回溯，恢复现场，这个位置回溯必定也是空
            board[x][y] = temp;
            setOrRecoverBoard(x, y, num);
        }
        return false;
    }

    private static void setOrRecoverBoard(int x, int y, int val) {
        //在棋盘上(x,y)放置val或者移出val，如果是放置，就等价于 row[x] -= 1 << val；如果是移出就等价于 row[x] += 1 << val;
        row[x] ^= 1 << val;
        col[y] ^= 1 << val;
        cell[getCellIndex(x, y)] ^= 1 << val;
    }

    private static void init() {
        //预处理出来各个状态的lowbit得到的数
        for (int i = 0; i < N; i++) lowbitNum[1 << i] = i;
        //统计出每个状态可以填的数量
        for (int i = 0; i < 1 << N; i++) {
            for (int j = i; j > 0; j -= lowbit(j)) {
                oneCount[i]++;
            }
        }
    }

    private static int getStatus(int x, int y) {
        return row[x] & col[y] & cell[getCellIndex(x, y)];
    }

    private static int lowbit(int n) {
        return n & -n;
    }

    private static int getCellIndex(int x, int y) {
        return x / 3 * 3 + y / 3;
    }
}
